/*
 * $Id: Parser.java,v 1.14 2003/06/29 10:52:30 znamenacek Exp $
 *
 * Copyright (c) Tomas Znamenacek
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 */

package net.sf.vofce.guts;

import java.util.List;
import java.util.Vector;
import java.util.Stack;
import java.util.Iterator;

import java.text.NumberFormat;
import java.text.ParsePosition;

/**
 * Converts <code>String</code> infix representation of some
 * function into postfix one. Also validates the input.
 *
 * @author Tomas Znamenacek
 */
public class Parser {

	//
	// Syntax check state machine states
	//
	protected static final int STATE_WAIT = 1;
	protected static final int STATE_FINISH = 2;
	protected static final int STATE_ARG = 3;
	
	/** The parsed string. */
	protected String input;
	
	/** Current position in the parsed string. */
	protected int pos;

	/** Current state of the state machine used for syntax checking. */
	protected int state;

	/** List of all the operators. */
	protected static OperatorList operators = OperatorList.getInstance();
	
	//
	// PUBLIC METHODS
	//
	
	/**
	 * Returns <code>true</code> iff the passed <code>String</code>
	 * parameter is a valid representation of some function.
	 */
	public boolean validates(String input) {

		try {
			Operator foo = buildTree(input);
			return true;
			
		} catch (Exception e) {

			return false;
		}
	}
	/**
	 * Chops the input into tokens, checks for its validity and
	 * converts it into postfix representation.
	 */
	public Operator buildTree(String input) throws Exception {

		this.input = input.toLowerCase();
		this.pos = 0;
		this.state = STATE_WAIT;
		
		return buildTree(tokenise());
	}

	//
	// PROTECTED METHODS
	//

	/**
	 * Returns next token from the input string.
	 */
	protected Token getNextToken() throws Exception {

		while (input.charAt(pos) == ' ') { pos++; }
		
		if (Character.isDigit(input.charAt(pos))) {
			
			NumberFormat nf = NumberFormat.getInstance();
			nf.setParseIntegerOnly(false);

			ParsePosition position = new ParsePosition(pos);
			Number number = nf.parse(input, position);

			if (position.getErrorIndex() != -1) {
				throw new InvalidNumber(position.getErrorIndex());
			}
		
			pos = position.getIndex();			
			return new NumberOperator(number);

		} else if (input.charAt(pos) == '(') {

			pos++;
			return new OpeningBracket();
			
		} else if (input.charAt(pos) == ')') {

			pos++;
			return new ClosingBracket();

		} else {

			String found = "";
			String chunk = input.substring(pos, input.length());
			String[] syntaxes = operators.syntaxes();
			
			for (int i = 0; i < syntaxes.length; i++) {

				if (chunk.startsWith(syntaxes[i]) && (found.length() < syntaxes[i].length())) {
					found = syntaxes[i];
				}
			}

			if (found.equals("")) { throw new UnknownOperator(pos); }

			pos += found.length();
			return operators.get(found).getFreshInstance();
		}
	}
	/**
	 * Converts the <code>String</code> representation of the function into
	 * an array of tokens.
	 * Also checks whether the input is well-formed infix representation of
	 * some function. Removes syntactic sugar (like <code>3x &rarr; 3*x</code>).
	 */
	protected Token[] tokenise() throws Exception {

		List output = new Vector();
		Token nextToken;
		int bracket = 0;

		BinaryOperator multiply = (BinaryOperator) operators.get("*");
	
		UnaryOperator unaryMinus = new UnaryOperator(6, "-{0}", "-{0}", "<mo>-</mo>{0}") {
			public double operation(double a) {
				return -a;
			}
		};
		
		do {
			nextToken = getNextToken(); 

			if (nextToken instanceof OpeningBracket) {

				bracket++;
			}

			if (nextToken instanceof ClosingBracket) {

				bracket--;
			}

			if (state == STATE_WAIT) {

				if (nextToken.equals(operators.get("-"))) {
					output.add(unaryMinus.getFreshInstance());
					continue;
				}
				
				if (nextToken instanceof OpeningBracket) {
					output.add(nextToken);
					continue;
				}

				if (nextToken instanceof NullaryOperator) {
					output.add(nextToken);
					state = STATE_FINISH;
					continue;
				}

				if (nextToken instanceof UnaryOperator) {
					output.add(nextToken);
					state = STATE_ARG;
					continue;
				}

				throw new SyntaxError(pos);
				
			} else if (state == STATE_FINISH) {

				if (nextToken instanceof ClosingBracket) {
					output.add(nextToken);
					continue;
				}

				if (nextToken instanceof NullaryOperator) {
					output.add(multiply.getFreshInstance());
					output.add(nextToken);
					continue;
				}

				if (nextToken instanceof OpeningBracket) {
					output.add(multiply.getFreshInstance());
					output.add(nextToken);
					state = STATE_WAIT;
					continue;
				}

				if (nextToken instanceof BinaryOperator) {
					output.add(nextToken);
					state = STATE_ARG;
					continue;
				}

				if (nextToken instanceof UnaryOperator) {
					output.add(multiply.getFreshInstance());
					output.add(nextToken);
					state = STATE_ARG;
					continue;
				}
				
				throw new SyntaxError(pos);

			} else { // state == STATE_ARG

				if (nextToken instanceof UnaryOperator) {
					output.add(nextToken);
					continue;
				}

				if (nextToken instanceof NullaryOperator) {
					output.add(nextToken);
					state = STATE_FINISH;
					continue;
				}

				if (nextToken instanceof OpeningBracket) {
					output.add(nextToken);
					state = STATE_WAIT;
					continue;
				}
				
				throw new SyntaxError(pos);
			}

		} while (pos < input.length());

		if (state != STATE_FINISH) { throw new SyntaxError(); }
		if (bracket != 0) { throw new UnbalancedBrackets(); }
		
		return (Token[]) output.toArray(new Token[] {});
	}

	/**
	 * Converts the infix representation of a function into
	 * a postfix one.
	 */
	protected Operator buildTree(Token[] input) throws Exception {

		Stack arguments = new Stack();
		Stack stack = new Stack();

		for (int i = 0; i < input.length; i++) {

			if (input[i] instanceof NullaryOperator) {

				buildNode((Operator) input[i], arguments);
				continue;
			}
			if (input[i] instanceof OpeningBracket) {

				stack.push(input[i]);
				continue;
			}

			// Closing bracket pops everything from the
			// stack until matching bracket found, matching
			// bracket is removed.
			if (input[i] instanceof ClosingBracket) {

				while (! (stack.peek() instanceof OpeningBracket)) {
					buildNode((Operator) stack.pop(), arguments);
				}

				Object foo = stack.pop();
				continue;
			}

			// Operator with arity != 0 pops operators with same
			// or higher priority from the stack, then pushes
			// itself onto the stack.
			Operator op = (Operator) input[i];
		
			while ((!stack.empty()) &&
					(stack.peek() instanceof Operator) &&
					(((Operator) stack.peek()).getPriority() >= op.getPriority())) {
			
				buildNode((Operator) stack.pop(), arguments);
			}

			stack.push(op);
		}
	
		while (! stack.empty()) { buildNode((Operator) stack.pop(), arguments); }
		if (arguments.size() != 1) { throw new Exception(); }
		
		return (Operator) arguments.pop();
	}

	protected void buildNode(Operator node, Stack arguments) throws Exception {

		if (node instanceof NullaryOperator) {

			arguments.push(node);
			return;
		}
		
		if (node instanceof UnaryOperator) {

			node.setLeftChild((Operator) arguments.pop());
			arguments.push(node);
			return;
		}

		if (node instanceof BinaryOperator) {

			node.setRightChild((Operator) arguments.pop());
			node.setLeftChild((Operator) arguments.pop());
			arguments.push(node);
			return;
		}
	}
}
